https://leetcode.com/problems/rearrange-string-k-distance-apart/

给定一个字符串 s s s，其长度为 l l l，给定一个非负整数 k k k，问是否可以将其重排，使得相距 k k k范围内的两个字母都不相等（恰好相距 k k k是可以的，但再近的就不能相等了）。如果能，返回重排后的字符串；否则返回空串。题目保证只含小写英文字母。

思路是贪心。想象我们有 l l l个空位，将其分成 l / k l/k l/k个大块，每个大块长度为 l / k l/k l/k，如果后面还有空位没有分配，则它们在最后成为一个长度小于 l / k l/k l/k的大块。那我们不允许在同一个大块里存在相同的字符，所以我们的策略是，在每个大块里，依次填出现次数最多的 k k k个字符（如果到了最后一个大块了，那么这个大块的长度小于 k k k，则填写的字符数小于 k k k。这里选择出现最多的 k k k个字符，原因在于直觉上来说，”潜在地“它们占用的地方最多，需要最先被分配掉），填写的时候，要按照字典序填，这样保证块与块之间也不会产生相同字母距离小于 k k k的情况（这里的字典序实际上可以是任何一种序，只需要是 26 26 26个英文字母的全序关系即可，不一定要按照 a b c d abcd abcd的顺序）。填完第一个大块之后，用相同的手法填第二个大块，以此类推。如果发现填某个大块的时候，比如该大块长度为 k k k，但发现挑不出 k k k个未使用的不同字母了，则不存在方案，返回空串。这个算法其实是这么个意思，每次挑选的字母都是还剩余的字母中，出现次数最多，前面 k k k距离范围内没有，并且字典序最小的字母，进行拼接。一旦发现挑不出来满足条件的了，就说明无解，返回空串。

算法正确性证明： 首先，如果算法返回一个非空串，则必然存在合法方案，这一点是显然的（因为算法已经构造出来了）。下面证明如果存在合法方案，则一定不会返回空串。如果 l ≤ k l\le k l≤k，存在合法方案意味着每个字母只出现 1 1 1次，显然算法不会返回空串，结论成立。假设对于 l < n l